package com.tgy.dynamic.programming;

/**
 * @Author: tgy
 * @Date: 2020-11-12 17:05
 *
 * longest common subsequence
 */
public class LCS {

    /**
     * 使用一维数组
     * @param leftArr
     * @param rightArr
     * @return
     */
    public int lcs(int[] leftArr,int[] rightArr) {

        int[] row = leftArr;
        int[] col = rightArr;

        if (leftArr.length < rightArr.length) {

            row = rightArr;
            col = leftArr;
        }

        int[]dp = new int[col.length+ 1];

        int dpj,preDpj;
        for (int i = 1; i <= row.length; i++) {

            dpj = 0;
            for (int j = 1; j <= col.length; j++) {

                // 把前一个dpj - 1 赋值
                preDpj = dpj;
                // 保存当前的dp[j]
                dpj = dp[j];

                if (row[i - 1] == col[j - 1]) {

                    dp[j] = preDpj + 1;
                }else {

                    dp[j] = Math.max(dp[j-1],dp[j]);
                }
            }
        }

        return dp[col.length];
    }

    /**
     * 使用滚动数组
     * @param leftArr
     * @param rightArr
     * @return
     */
//    public int lcs02(int[] leftArr,int[] rightArr) {
//
//
//        int[][] dp = new int[2][rightArr.length+1];
//
//        int row,preRow;
//        for (int i = 1; i <= leftArr.length; i++) {
//
//            // 当前行
//            row = i & 1;
//            // 上一行
//            preRow = (i - 1) & 1;
//            for (int j = 1; j <= rightArr.length; j++) {
//
//                if (leftArr[i - 1] == rightArr[j - 1]) {
//
//                    dp[row][j] = dp[preRow][j - 1] + 1;
//                }else {
//
//                    dp[row][j] = Math.max(dp[preRow][j],dp[row][j-1]);
//                }
//            }
//        }
//
//        return dp[leftArr.length & 1][rightArr.length];
//    }

    /**
     * 使用二维数组实现
     * @param leftArr
     * @param rightArr
     * @return
     */
//    public int lcs01(int[] leftArr,int[] rightArr) {
//
//
//        int[][] dp = new int[leftArr.length+1][rightArr.length+1];
//
//        for (int i = 1; i <= leftArr.length; i++) {
//
//            for (int j = 1; j <= rightArr.length; j++) {
//
//                if (leftArr[i - 1] == rightArr[j - 1]) {
//
//                    dp[i][j] = dp[i - 1][j - 1] + 1;
//                }else {
//
//                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
//                }
//            }
//        }
//
//        return dp[leftArr.length][rightArr.length];
//    }
}
